package find_way;

import path_finding.AStar;
import path_finding.JPS;
import path_finding.PathFinding;
import path_finding.XyTrans;

import javax.swing.*;
import javax.swing.Timer;
import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.*;
import java.util.List;

class JPSShow extends JPanel implements ActionListener {
    private static final int GRID_SIZE = 100;
    private static final int CELL_SIZE = 10;
    private static final int PADDING = 20;
    private int current;
    private int target;
    private Timer timer;
    private Set<Integer> obstacleSet = new HashSet<>();
    private List<Integer> findWay = new ArrayList<>();
    private Iterator<Integer> pathIterator;
    private List<Integer> drawWay = new LinkedList<>();
    private int[][] visited;

    JPSShow() {
        timer = new Timer(100, this);

        /*
        current = 11;
        target = 77;
        obstacleSet.add(10);
        obstacleSet.add(12);
        obstacleSet.add(21);
        obstacleSet.add(23);
        obstacleSet.add(14);
        obstacleSet.add(41);
        obstacleSet.add(42);
        obstacleSet.add(43);
        obstacleSet.add(44);
        obstacleSet.add(45);
        obstacleSet.add(46);
        obstacleSet.add(47);
        obstacleSet.add(48);
        obstacleSet.add(49);
        obstacleSet.add(65);
        obstacleSet.add(66);
        obstacleSet.add(67);
        obstacleSet.add(68);
        obstacleSet.add(75);
        obstacleSet.add(85);
        obstacleSet.add(78);
        obstacleSet.add(88);
        obstacleSet.add(94);
         */
        // 复杂寻路测试用例 - 100x100网格地图
        obstacleSet.add(202);    // 起始障碍物
        obstacleSet.add(203);
        obstacleSet.add(215);
        obstacleSet.add(225);
        obstacleSet.add(234);
        obstacleSet.add(245);

// 创建迷宫式通道
        for (int i = 10; i < 90; i += 2) {
            obstacleSet.add(i * 100 + 30);  // 垂直障碍墙
        }

// 添加锯齿形障碍物
        for (int i = 15; i < 85; i += 3) {
            obstacleSet.add(i * 100 + 45 + (i % 2) * 10);
        }

// 创建多个房间和走廊
        int[] roomCenters = {3030, 5050, 7070, 3060, 6080};
        for (int center : roomCenters) {
            int x = center / 100;
            int y = center % 100;
            for (int i = -5; i <= 5; i++) {
                for (int j = -5; j <= 5; j++) {
                    if (Math.abs(i) == 5 || Math.abs(j) == 5) {
                        obstacleSet.add((x + i) * 100 + (y + j));
                    }
                }
            }
            // 添加门廊
            obstacleSet.remove((x + 5) * 100 + y);
            obstacleSet.remove((x - 5) * 100 + y);
        }

// 创建必须绕行的长障碍物
        for (int i = 20; i < 80; i++) {
            obstacleSet.add(4000 + i);  // 水平长墙
            obstacleSet.add(i * 100 + 60);  // 垂直长墙
        }

// 添加一些孤立障碍物
        obstacleSet.add(1515);
        obstacleSet.add(2525);
        obstacleSet.add(3535);
        obstacleSet.add(4545);
        obstacleSet.add(5555);
        obstacleSet.add(6565);
        obstacleSet.add(7575);
        obstacleSet.add(8585);

// 设置起点和终点（需要绕行多个障碍物）
        current = 1111;    // 起点 (11,11)
        target = 8888;      // 终点 (88,88)

        runJPS();
        timer.start();
    }

    // 方向常量
    private static final int[][] DIRECTIONS = {
            {-1, -1}, {-1, 0}, {-1, 1},
            {0, -1}, {0, 1},
            {1, -1}, {1, 0}, {1, 1}
    };

    private int heuristic(int from, int to) {
        int fromX = from % GRID_SIZE;
        int fromY = from / GRID_SIZE;
        int toX = to % GRID_SIZE;
        int toY = to / GRID_SIZE;
        int disX = Math.abs(toX - fromX);
        int disY = Math.abs(toY - fromY);
        int diagonal = Math.min(disX, disY);
        int straight = Math.abs(disX - disY);
        int distance = diagonal * 14 + straight * 10;
        return distance;
    }

    private boolean isWalkable(int cellId) {
        if (cellId < 0 || cellId >= GRID_SIZE * GRID_SIZE) return false;
        return !obstacleSet.contains(cellId);
    }

    private boolean isWalkable(int x, int y) {
        if (x < 0 || x >= GRID_SIZE || y < 0 || y >= GRID_SIZE) return false;
        return isWalkable(y * GRID_SIZE + x);
    }

    // JPS核心：跳跃函数
    private Integer jump(int x, int y, int dx, int dy, int targetId) {
        int currentId = y * GRID_SIZE + x;
        if (!isWalkable(x, y)) {
            return null; // 碰到障碍物
        }

        if (currentId == targetId) {
            return currentId; // 找到目标
        }

        // 检查强迫邻居
        if (hasForcedNeighbor(x, y, dx, dy)) {
            System.out.println(currentId + "有强迫邻居");
            return currentId;
        }

        // 对角线移动的特殊处理
        if (dx != 0 && dy != 0) {
            // 尝试水平方向跳跃
            if (jump(x + dx, y, dx, 0, targetId) != null) {
                System.out.println(currentId + "水平方向有跳点");
                return currentId;
            }
            // 尝试垂直方向跳跃
            if (jump(x, y + dy, 0, dy, targetId) != null) {
                System.out.println(currentId + "垂直方向有跳点");
                return currentId;
            }
        }

        // 继续沿着当前方向跳跃 (这里有个前提，对角线需要考虑穿墙角问题, 所以要加上判断)
        if (dx == 0 || dy == 0 || isWalkable(x + dx, y) || isWalkable(x, y + dy)) {
            return jump(x + dx, y + dy, dx, dy, targetId);
        }
        return null;
    }

    private boolean hasForcedNeighbor(int x, int y, int dx, int dy) {
        if (dx != 0 && dy != 0) {
            // 对角线移动的强迫邻居检查
            if ((!isWalkable(x - dx, y) && isWalkable(x - dx, y + dy) && isWalkable(x, y + dy)) ||
                    (!isWalkable(x, y - dy) && isWalkable(x + dx, y - dy) && isWalkable(x + dx, y))) {
                return true;
            }
        } else if (dx != 0) {
            // 水平移动的强迫邻居检查
            if (isWalkable(x + dx, y + dy)) {
                if ((!isWalkable(x, y - 1) && isWalkable(x + dx, y - 1)) ||
                        (!isWalkable(x, y + 1) && isWalkable(x + dx, y + 1))) {
                    return true;
                }
            }
        } else if (dy != 0) {
            // 垂直移动的强迫邻居检查
            if (isWalkable(x + dx, y + dy)) {
                if ((!isWalkable(x - 1, y) && isWalkable(x - 1, y + dy)) ||
                        (!isWalkable(x + 1, y) && isWalkable(x + 1, y + dy))) {
                    return true;
                }
            }
        }
        return false;
    }

    private List<int[]> getSearchDirection(Node node) {
        // 获取跳点方向
        List<int[]> directions = new ArrayList<>();
        int x = node.x;
        int y = node.y;
        if (node.parent == null) {
            // 起始节点，检查所有方向
            for (int[] dir : DIRECTIONS) {
                if (dir[0] != 0 && dir[1] != 0 && !isWalkable(x + dir[0], y) && !isWalkable(x, y + dir[1])) {
                    continue;
                }
                if (isWalkable(x + dir[0], y + dir[1])) {
                    directions.add(dir);
                }
            }
        } else {
            // 根据父节点方向确定需要检查的方向
            int px = node.dirX;
            int py = node.dirY;

            if (px != 0 && py != 0) {
                // 三个正常探索
                boolean F = isWalkable(x, y + py);
                boolean R = isWalkable(x + px, y);
                boolean B = isWalkable(x, y - py);
                boolean L = isWalkable(x - px, y);
                if (R) {
                    directions.add(new int[]{px, 0});
                }
                if (F) {
                    directions.add(new int[]{0, py});
                }
                if ((R || F) && isWalkable(x + px, y + py)) {
                    directions.add(new int[]{px, py});
                }

                // 两个强迫邻居 !L即有阻挡 F就是对角线移动时，两边不能同时阻挡
                if (!L && F && isWalkable(x - px, y + py)) {
                    directions.add(new int[]{-px, py});
                }
                if (!B && R && isWalkable(x + px, y - py)) {
                    directions.add(new int[]{px, -py});
                }
            } else {
                if (px != 0) {
                    // 来自水平方向 正常探索
                    if (isWalkable(x + px, y)) {
                        directions.add(new int[]{px, 0});

                        //两个强迫邻居
                        if (!isWalkable(x, y - 1) && isWalkable(x + px, y - 1)) {
                            directions.add(new int[]{px, -1});
                        }
                        if (!isWalkable(x, y + 1) && isWalkable(x + px, y + 1)) {
                            directions.add(new int[]{px, 1});
                        }
                    }
                    /*  放这里就会出现穿越对角问题
                    //两个强迫邻居
                    if (!isWalkable(x, y - 1) && isWalkable(x + px, y - 1)) {
                        directions.add(new int[]{px, -1});
                    }
                    if (!isWalkable(x, y + 1) && isWalkable(x + px, y + 1)) {
                        directions.add(new int[]{px, 1});
                    }
                     */
                } else {
                    // 来自垂直方向
                    if (isWalkable(x, y + py)) {
                        directions.add(new int[]{0, py});
                        //下面这两个强迫邻居的判断要放在这个if里面
                        if (!isWalkable(x + 1, y) && isWalkable(x + 1, y + py)) {
                            directions.add(new int[]{1, py});
                        }
                        if (!isWalkable(x - 1, y) && isWalkable(x - 1, y + py)) {
                            directions.add(new int[]{-1, py});
                        }
                    }
                }
            }
        }
        return directions;
    }

    public int getNodeId(Node node) {
        return node.x + node.y * GRID_SIZE;
    }

    private void runJPS() {
        PathFinding pathFinding = new JPS();
        pathFinding.setXyTrans(new XyTrans() {
            @Override
            public int toId(int x, int y) {
                return x + y * GRID_SIZE;
            }

            @Override
            public int[] toXy(int id) {
                int[] xy = new int[2];
                xy[0] = id % GRID_SIZE;
                xy[1] = id / GRID_SIZE;
                return xy;
            }
        });
        int grid[][] = new int[GRID_SIZE][GRID_SIZE];
        for (int obstacle : obstacleSet) {
            int x = obstacle % GRID_SIZE;
            int y = obstacle / GRID_SIZE;
            grid[x][y] = 1;
        }
        visited = new int[GRID_SIZE][GRID_SIZE];
        findWay = pathFinding.findPath(grid, current % GRID_SIZE, current / GRID_SIZE,
                target % GRID_SIZE, target / GRID_SIZE, visited);
        System.out.println("AStar 找到最优路径长度" + findWay.size());
        pathIterator = findWay.iterator();

//        findWay.clear();
//        visitedNodes.clear();
//        visitedNodes.add(current);

//        PriorityQueue<Node> openSet = new PriorityQueue<>(Comparator.comparingInt(o -> o.g + o.h));
//        Map<Integer, Node> allNodes = new HashMap<>();
//        Set<Integer> closedSet = new HashSet<>();

//        Node startNode = new Node(current % GRID_SIZE, current / GRID_SIZE, 0, heuristic(current, target));
//        openSet.add(startNode);
//        allNodes.put(current, startNode);

//        boolean found = false;

//        while (!openSet.isEmpty()) {
//            Node currentNode = openSet.poll();
//            int currentId = getNodeId(currentNode);
//            System.out.println("选中" + currentId);

//            if (currentId == target) {
//                found = true;
//                break;
//            }

//            closedSet.add(currentId);

//            List<int[]> directions = getSearchDirection(currentNode);
//            int currentX = currentId % GRID_SIZE;
//            int currentY = currentId / GRID_SIZE;

//            for (int[] dir : directions) {
//                System.out.println("-------------------可选" + (currentX + dir[0] + (currentY + dir[1]) * GRID_SIZE));
//            }

//            // 对每个方向进行跳跃
//            for (int[] dir : directions) {
//                Integer jumpPointId = jump(currentX + dir[0], currentY + dir[1], dir[0], dir[1], target);

//                if (jumpPointId != null && !closedSet.contains(jumpPointId)) {
//                    int jumpX = jumpPointId % GRID_SIZE;
//                    int jumpY = jumpPointId / GRID_SIZE;

//                    int disX = Math.abs(jumpX - currentX);
//                    int disY = Math.abs(jumpY - currentY);
//                    int diagonal = Math.min(disX, disY);
//                    int straight = Math.abs(disX - disY);
//                    int distance = diagonal * 14 + straight * 10;
//                    int newG = currentNode.g + distance;
//                    System.out.printf("jumpTo=%d, current=%d, dir=[%d,%d]\n", jumpPointId, currentId, dir[0], dir[1]);

//                    Node jumpNode = allNodes.get(jumpPointId);
//                    if (jumpNode == null) {
//                        jumpNode = new Node(jumpX, jumpY, newG, heuristic(jumpPointId, target),
//                                currentNode);
//                        jumpNode.dirX = dir[0];
//                        jumpNode.dirY = dir[1];
//                        openSet.add(jumpNode);
//                        allNodes.put(jumpPointId, jumpNode);
//                    } else if (newG < jumpNode.g) {
//                        jumpNode.g = newG;
//                        jumpNode.parent = currentNode;
//                        jumpNode.dirX = dir[0];
//                        jumpNode.dirY = dir[1];
//                        // 需要重新加入优先队列以更新顺序
//                        openSet.remove(jumpNode);
//                        openSet.add(jumpNode);
//                    }
//                }
//            }
//        }

//        if (found) {
//            // 重建路径
//            Node node = allNodes.get(target);
//            while (node != null) {
//                findWay.addFirst(getNodeId(node));
//                node = node.parent;
//            }
//            expandWay();
//            pathIterator = findWay.iterator();
//            System.out.println("JPS路径长度: " + (findWay.size() - 1));
//            System.out.println("访问节点数: " + visitedNodes.size());
//        } else {
//            System.out.println("JPS找不到路径!");
//        }
    }

    private void expandWay() {
        List<Integer> expandWay = new ArrayList<>();
        expandWay.add(findWay.get(0));
        for (int i = 0; i < findWay.size() - 1; ++ i) {
            int current = findWay.get(i);
            int next = findWay.get(i + 1);
            fillWay(current, next, expandWay);
        }
        findWay = expandWay;
    }

    private void fillWay(int from, int to, List<Integer> way) {
        int fromX = from % GRID_SIZE;
        int fromY = from / GRID_SIZE;
        int toX = to % GRID_SIZE;
        int toY = to / GRID_SIZE;
        System.out.printf("填充[%d,%d] -> [%d,%d]\n", fromX, fromY, toX, toY);

        int dx = 0;
        if (toX != fromX) {
            dx = (toX - fromX) / Math.abs(toX - fromX);
        }
        int dy = 0;
        if (fromY != toY) {
            dy = (toY - fromY) / Math.abs(toY - fromY);
        }

        while (fromX != toX || fromY != toY) {
            fromX += dx;
            fromY += dy;
            System.out.printf("填充了[%d,%d]\n", fromX, fromY);
            way.add(fromY * GRID_SIZE + fromX);
        }
    }

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);
        setBackground(Color.WHITE);
        g.setColor(Color.LIGHT_GRAY);

        // 绘制网格
        for (int i = 0; i <= GRID_SIZE; i++) {
            int y = PADDING + i * CELL_SIZE;
            g.drawLine(PADDING, y, PADDING + GRID_SIZE * CELL_SIZE, y);
        }
        for (int i = 0; i <= GRID_SIZE; i++) {
            int x = PADDING + i * CELL_SIZE;
            g.drawLine(x, PADDING, x, PADDING + GRID_SIZE * CELL_SIZE);
        }

        // 绘制当前路径
        g.setColor(Color.BLUE);
        for (int current : drawWay) {
            int filledCellX = current % GRID_SIZE;
            int filledCellY = current / GRID_SIZE;
            int x = PADDING + filledCellX * CELL_SIZE;
            int y = PADDING + filledCellY * CELL_SIZE;
            g.fillRect(x + 1, y + 1, CELL_SIZE - 1, CELL_SIZE - 1);
        }

        // 绘制访问过的节点（浅蓝色）
        g.setColor(new Color(200, 230, 255));
        for (int i = 0; i < visited.length; ++ i) {
            for (int j = 0; j < visited[i].length; ++ j) {
                if (visited[i][j] != 1) continue;
                int x = PADDING + i * CELL_SIZE;
                int y = PADDING + j * CELL_SIZE;
                g.fillRect(x + 1, y + 1, CELL_SIZE - 1, CELL_SIZE - 1);
            }
        }

        // 绘制障碍物
        g.setColor(Color.BLACK);
        for (int obstacle : obstacleSet) {
            int filledCellX = obstacle % GRID_SIZE;
            int filledCellY = obstacle / GRID_SIZE;
            int x = PADDING + filledCellX * CELL_SIZE;
            int y = PADDING + filledCellY * CELL_SIZE;
            g.fillRect(x + 1, y + 1, CELL_SIZE - 1, CELL_SIZE - 1);
        }

        // 绘制目标点
        g.setColor(Color.RED);
        int filledCellX = target % GRID_SIZE;
        int filledCellY = target / GRID_SIZE;
        int x = PADDING + filledCellX * CELL_SIZE;
        int y = PADDING + filledCellY * CELL_SIZE;
        g.fillRect(x + 1, y + 1, CELL_SIZE - 1, CELL_SIZE - 1);

        // 绘制信息
        g.setColor(Color.BLACK);
        g.drawString("Jump Point Search (JPS) - 20x20 Grid", PADDING, PADDING - 5);
    }

    @Override
    public Dimension getPreferredSize() {
        int size = PADDING * 2 + GRID_SIZE * CELL_SIZE;
        return new Dimension(size, size + 30);
    }

    @Override
    public void actionPerformed(ActionEvent e) {
        if (pathIterator != null && pathIterator.hasNext()) {
            current = pathIterator.next();
            drawWay.add(current);
            repaint();
        }
    }
}

public class JPSMain {
    public static void main(String[] args) {
        SwingUtilities.invokeLater(() -> {
            JFrame frame = new JFrame("Jump Point Search Demo");
            frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
            frame.add(new JPSShow());
            frame.pack();
            frame.setLocationRelativeTo(null);
            frame.setVisible(true);
        });
    }
}